/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定单词列表（<=15000)，每个单词(1<=长<=10)有权重，i. f的功能是：含有指定前缀和后缀的词的最大权重，如果没有，返回-1
 * 
 * @author zhong
 *
 */
public class PrefixandSuffixSearch {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] words = { "cabaabaaaa", "cabaabaaaa", "cabaabaaaa", "cabaabaaaa", "cabaabaaaa", "cabaabaaaa",
				"cabaabaaaa", "cabaabaaaa", "cabaabaaaa", "cabaabaaaa" };
		String prefix = "a", suffix = "e";

		WordFilter obj = new WordFilter(words);
		System.out.println(obj.f(prefix, suffix));
		prefix = "c";
		suffix = "aa";
		System.out.println(obj.f(prefix, suffix));
	}

	static class WordFilter {

		static class Node {
			Node[] childs = new Node[26];
			Map<String, Integer> set = new HashMap<>();
		}

		Node root1;
		Node root2;

		public WordFilter(String[] words) {
			root1 = new Node();
			root2 = new Node();
			for (int i = 0; i < words.length; i++) {
				Node cur = root1;
				String string = words[i];
				// 对应权重改变为i__要把下面每个节点都改成i！！！！，所以，即使有了相同的字符串，还是要一个个节点搜索
				// if (cur.set.containsKey(string)) {
				// cur.set.put(string, i);
				// } else {
				for (int j = 0; j < string.length(); j++) {
					if (cur.childs[string.charAt(j) - 'a'] == null) {
						cur.childs[string.charAt(j) - 'a'] = new Node();
					}
					cur.set.put(string, i);
					cur = cur.childs[string.charAt(j) - 'a'];
				}
				cur.set.put(string, i);

				cur = root2;
				// if (cur.set.containsKey(string)) {// 对应权重改变为i
				// cur.set.put(string, i);
				// } else {
				for (int j = string.length() - 1; j >= 0; j--) {
					if (cur.childs[string.charAt(j) - 'a'] == null) {
						cur.childs[string.charAt(j) - 'a'] = new Node();
					}
					cur.set.put(string, i);
					cur = cur.childs[string.charAt(j) - 'a'];
				}
				cur.set.put(string, i);
			}
		}

		public int f(String prefix, String suffix) {
			Node cur = root1;
			for (int j = 0; j < prefix.length(); j++) {
				if (cur.childs[prefix.charAt(j) - 'a'] == null) {// 如果不包含，找不到含有指定前缀的词，则返回-1
					return -1;
				}
				cur = cur.childs[prefix.charAt(j) - 'a'];
			}
			Node cur2 = root2;
			for (int j = suffix.length() - 1; j >= 0; j--) {
				if (cur2.childs[suffix.charAt(j) - 'a'] == null) {
					return -1;
				}
				cur2 = cur2.childs[suffix.charAt(j) - 'a'];
			}
			System.out.println(cur.set.toString());
			System.out.println(cur2.set);
			int res = -1;
			for (String string : cur.set.keySet()) {
				if (cur2.set.keySet().contains(string)) {
					res = Math.max(res, cur.set.get(string));
				}
			}
			return res;
		}
	}
}
